﻿//
// Created by Freeman on 2022/3/8.
//

#include <iostream>
#include <map>
#include <vector>

#include "../Headers/Graph.hpp"

using namespace std;

void PAT_A1003::solve() {
    // 接收输入并初始化数据结构
    int nVex, nRoads, srcID, destID;
    cin >> nVex >> nRoads >> srcID >> destID;
    int *nPaths = new int[nVex], // 源点到达此顶点的最短路径条数
            *localTeams = new int[nVex], // 每个顶点的本地救援队数量
            *nTeams = new int[nVex]; // 能够带到此顶点的最大的救援队数量
    fill(nPaths, nPaths + nVex, 0);
    nPaths[srcID] = 1;
    int *dist = new int[nVex];
    fill(dist, dist + nVex, INT32_MAX);
    dist[srcID] = 0;
    bool *visit = new bool[nVex];
    fill(visit, visit + nVex, false);
    vector<vector<int>> adjMat(nVex, vector<int>(nVex, INT32_MAX)); // 邻接矩阵初始化为无穷大
    for (int i = 0; i < nVex; i++) adjMat[i][i] = 0;
    for (int i = 0; i < nVex; i++) {
        int tmpTeams;
        cin >> tmpTeams;
        localTeams[i] = nTeams[i] = tmpTeams;
    }
    for (int i = 1; i <= nRoads; i++) {
        int v, w, len;
        cin >> v >> w >> len;
        adjMat[v][w] = adjMat[w][v] = len;
    }

    // Dijkstra
    while (true) {
        // 寻找距离源点最近的未访问过的顶点
        int minDist = INT32_MAX, v = -1;
        for (int i = 0; i < nVex; i++) {
            if (visit[i]) continue;
            if (dist[i] < minDist) {
                minDist = dist[i];
                v = i;
            }
        }
        visit[v] = true;
        if (v == destID) break; // 寻找到终点，算法终止
        for (int w = 0; w < nVex; w++) { // 遍历未访问过的邻接零点
            if (visit[w] || adjMat[v][w] == INT32_MAX) continue;
            if (dist[w] > dist[v] + adjMat[v][w]) { // 经由v到w距离更短
                dist[w] = dist[v] + adjMat[v][w];
                nPaths[w] = nPaths[v]; // 覆盖路径数
                nTeams[w] = localTeams[w] + nTeams[v]; // 覆盖救援队数
            }
            else if (dist[w] == dist[v] + adjMat[v][w]) { // 发现多条最短路径
                nPaths[w] += nPaths[v]; // 最短路径数增加
                if (nTeams[v] + localTeams[w] > nTeams[w]) {
                    nTeams[w] = nTeams[v] + localTeams[w]; // 如果从v能带来更多的救援队，则更新救援队数量
                }
            }
        }
    }

    cout << nPaths[destID] << " " << nTeams[destID];
    delete[] nPaths;
    delete[] localTeams;
    delete[] nTeams;
    delete[] dist;
    delete[] visit;
}

void PAT_A1003_Problematic::solve() {
    int srcDestDist = dijkstra(); // 求源点到终点的最短距离，并找出每个点距离源点的最短距离和距离终点的最短距离
    vector<vector<int>>& adjMat = *adjMatPtr;
    map<int, Node*> distNodeMap; // 用作优先队列
    distNodeMap.insert(pair<int, Node*>(vertices[srcID].srcDist, &vertices[srcID]));
    bool* visited = new bool[nVex];
    fill(visited, visited + nVex, false);
    while (true) {
        int v = distNodeMap.begin()->second->id; // 每次选取距离源点最近的顶点出队
        distNodeMap.erase(distNodeMap.begin());
        Node& nodeV = vertices[v];
        if (nodeV.destFlag) break; // 终点出队标志算法结束
        for (int w = 0; w < nVex; w++) {
            if (!visited[w] && adjMat[v][w] < INT32_MAX) { // 寻找邻接于v且未访问的顶点w
                Node& nodeW = vertices[w];
                if (nodeV.srcDist + adjMat[v][w] + nodeW.destDist == srcDestDist) { // 存在包含v->w这一段路的最短路径
                    // 检查是否已在队列内
                    bool inMap = false;
                    for (auto pair : distNodeMap) {
                        if (pair.second->id == w) {
                            inMap = true;
                            break;
                        }
                    }
                    if (!inMap) distNodeMap.insert(pair < int, Node* >(nodeW.srcDist, &nodeW)); // 未入队则入队
                    nodeW.nPaths += nodeV.nPaths; // 因为存在经由v->w的最短路径，w上的最短路径数要加上v上的最短路径数
                    if (nodeV.nTeams + nodeW.localTeams > nodeW.nTeams)
                        nodeW.nTeams = nodeV.nTeams + nodeW.localTeams; // 如果从v方向能集结更多的救援队，则更新w上能集结的救援队数量
                }
            }
        }
    }

    Node& destNode = vertices[destID];
    cout << destNode.nPaths << " " << destNode.nTeams;
    delete[] visited;
}

int PAT_A1003_Problematic::dijkstra() {
    int srcDestDist;
    vector<vector<int>>& adjMat = *adjMatPtr;
    bool* visited = new bool[nVex];
    // 找出源点到所有点的最短距离
    fill(visited, visited + nVex, false);
    for (int epoch = 1; epoch <= nVex; epoch++) {
        int minDist = INT32_MAX, v; // v是本轮找到最短路径的顶点
        for (int i = 0; i < nVex; i++) { // 找出距离源点距离最近的顶点
            if (!visited[i] && vertices[i].srcDist < minDist) {
                v = i;
                minDist = vertices[i].srcDist;
            }
        }
        visited[v] = true;
        if (vertices[v].destFlag) srcDestDist = vertices[v].srcDist;
        for (int w = 0; w < nVex; w++) { // 更新与v邻接的顶点
            if (!visited[w] && adjMat[v][w] < INT32_MAX) { // v和w之间有路径
                if (vertices[v].srcDist + adjMat[v][w] < vertices[w].srcDist)
                    vertices[w].srcDist = vertices[v].srcDist + adjMat[v][w];
            }
        }
    }
    // 找出终点到所有点的最短距离
    fill(visited, visited + nVex, false);
    for (int epoch = 1; epoch <= nVex; epoch++) {
        int minDist = INT32_MAX, v; // v是本轮找到最短路径的顶点
        for (int i = 0; i < nVex; i++) { // 找出距离终点距离最近的顶点
            if (!visited[i] && vertices[i].destDist < minDist) {
                v = i;
                minDist = vertices[i].destDist;
            }
        }
        visited[v] = true;
        for (int w = 0; w < nVex; w++) { // 更新与v邻接的顶点
            if (!visited[w] && adjMat[v][w] < INT32_MAX) { // v和w之间有路径
                if (vertices[v].destDist + adjMat[v][w] < vertices[w].destDist)
                    vertices[w].destDist = vertices[v].destDist + adjMat[v][w];
            }
        }
    }

    delete[] visited;
    return srcDestDist;
}